package com.lxm.algorithm.lru;

import java.util.HashMap;
import java.util.Map;

public class LruCache<T> implements Lru<T> {
    private int size;
    public static final int DEFAULT_SIZE = 10;
    private Node head;
    private Node tail;
    private Map<String, Node> map;
    private int count;

    private class Node {
        public String key;
        public T value;
        public Node pre;
        public Node next;

        public Node(String key, T value) {
            this.key = key;
            this.value = value;
        }
    }

    private void moveHead(Node node) {
        if (node == null) {
            return;
        }
        if (head == node) {
            return;
        }
        Node pre = node.pre;
        Node next = node.next;
        if (pre != null) {
            pre.next = next;
        }
        if (next != null) {
            next.pre = pre;
        }
        if (tail == node) {
            tail = pre;
        }
        node.next = head;
        node.pre = null;
        head.pre = node;
        head = node;
        if (tail == null) {
            tail = node;
        }
    }

    private void addHead(Node node) {
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            node.pre = null;
            head.pre = node;
            head = node;
        }
        if (tail == null) {
            tail = node;
        }
    }

    private Node removeLast() {
        if (tail == null) {
            return null;
        }
        Node last = tail;
        Node pre = last.pre;
        pre.next = null;
        last.pre = null;
        tail = pre;
        return last;
    }

    public LruCache(int size) {
        this.size = size;
        this.map = new HashMap<>(size);
        this.count = 0;
    }

    public LruCache() {
        this(DEFAULT_SIZE);
    }

    @Override
    public T get(String key) {
        Node node = map.get(key);
        if (node != null) {
            moveHead(node);
            return node.value;
        }
        return null;
    }

    @Override
    public void set(String key, T value) {
        Node n = map.get(key);
        if (n == null) {
            n = new Node(key, value);
            addHead(n);
            if (count++ >= size) {
                Node last = removeLast();
                if (last != null) {
                    map.remove(last.key);
                    count--;
                }
            }
            map.put(key, n);
        } else {
            n.value = value;
            moveHead(n);
        }
    }
}
